An important parameter for assessing the quality of a binary digital communications link is its bit error rate (BER), that is the probability that a bit is incorrectly detected by a receiver. The BER is typically measured by transmitting over the link a long test sequence of bits, in principle selected at random, and counting how many are incorrectly received. A convenient method of both generating a test sequence and checking for correct reception is to use a pseudo-random binary sequence (PRBS).
A PRBS can be generated using a linear feedback shift register, as shown in FIG. 1. The output signal of the shift register is summed, modulo 2, with the outputs of selected intermediate stages of the register (e.g. using exclusive-OR gates), and the resulting signal is fed back to the input of the shift register. Appropriate selection of the stages whose outputs are combined by the exclusive-OR gates enables an n-stage shift register to generate a maximal length sequence with a period of 2.sup.n 1 bits, i.e. a PRBS. For example the feedback arrangement shown in FIG. 1 enables an 8-stage shift register to produce a maximal length sequence containing 255 bits. Since such a sequence is pseudo-random, it provides an effective test for exercising a communications link with a wide variety of bit patterns; nonetheless, the sequence is in fact fully deterministic, so it can be readily generated independently at the receiving end of the link to enable comparison of the sequence as received with an error-free reference version.
In the course of generating the PRBS the contents of the shift register will have as many different states (defined by the combination of the values in each of the shift-register stages) as there are bits in the maximal length sequence. Generation of the maximal length sequence can be commenced from any bit position in the sequence by initializing (`seeding`) the shift register with the set of values for its stages corresponding to that bit position.
The identity of the shift-register stages which provide feed-back to the input can be characterized by means of a polynomial expression with a coefficient of unity for each term corresponding to a stage which provides feedback. Thus the characteristic polynomial for the PRBS generator of FIG. 1 is: EQU x.sup.8 +x.sup.6 +x.sup.5 +x.sup.4 +1 (1)
The shift register arrangement shown in FIG. 1 generates a PRBS as a single serial bit-stream at its output. Techniques are also known, using multiple circuits like that in FIG. 1, for generating a PRBS in such a manner that a plurality of successive bits (i.e. a word) of the PRBS are available simultaneously, or in parallel. Thus, referring to FIG. 2, a PRBS can be considered to comprise successive words each of length w (w=8 in the Figure). If these words are written so that corresponding bits are aligned as in the table in FIG. 2, the sequence of bits in each column A to H (e.g. the sequence 01100000 . . . in column A) constitutes a decimation of the overall PRBS, with a decimation interval equal to the word length w. A set of linear feedback shift registers can be arranged with appropriate feedbacks (i.e. characteristic polynomial, which will be the same for each shift register) and initializing values so that they synchronously produce respective ones of the sequences in columns A to H. The outputs of these generators taken in parallel will then provide the overall PRBS a word at a time.
If w is a power of 2, the characteristic polynomial of each decimated sequence is the same as that for the overall PRBS. In addition, if the interval w has no common prime factors with the period of the overall PRBS, each decimated sequence is itself a PRBS of the same period, and the decimation is known as a proper decimation; otherwise the decimation is an improper decimation.
Hereinafter a sequence (maximal-length or not) of the kind that can be generated by the use of a linear feedback shift register is referred to as an LFSR sequence, irrespective of whether a conventional linear feedback shift register is actually used in the generation of the sequence. An arrangement which produces an LFSR sequence a word at a time is referred to herein as a pseudo-random pattern generator (PRPG). For convenience the following description will refer to a PRPG that is to be used for generating a PRBS.
PRPG's have a variety of uses. Thus, for example, the multi-bit PRPG output may be multiplexed into a single, serial PRBS having a bit rate higher than that of any of the individual sequence generators. Alternatively, a PRPG may be used for simultaneous testing of channels of a multi-bit (parallel) communications link.
As communications technology advances, it is generally necessary to provide PRPG's which operate faster and/or provide a PRBS having a longer period. In the past this has typically been accomplished by redesigning the sequence generators and/or increasing their number. The latter change itself can require a redesign of the sequence generators: if the bit rate of the multiplexed output of a PRPG for generating a given PRBS is increased by providing more sequence generators, the feedback connections for the sequence generators and the initializing values will in general need to be changed.
It is already known to provide a PRBS generator with a controllable number of stages and feedback arrangement. Thus, for example, SU 1 248 030 describes an arrangement in which a linear feedback shift register has each of its stages coupled via a multi-pole switch to a cascaded set of modulo-2 adders. Selective operation of the switch poles enables selection of which shift register stages contribute to a feedback signal generated by the cascaded modulo-2 adders. This feedback signal is directed via a second switch to a selected one of the shift register stages, according to the required number of active shift register stages; the second switch also supplies a clock signal to the currently active stages. A serious disadvantage with this arrangement is the use of a cascaded set of modulo-2 adders. The number of adders must be equal to the maximum possible number of shift register stages, and the feedback signal must propagate through all the adders irrespective of the number of stages which are currently active. This can impose a significant delay on the speed of generation of the feedback signal, and thus render the circuit unable to operate at the high speeds required for use with present and planned communications equipment.
Various designs for LFSR sequence generators are discussed in Design Considerations for Parallel Pseudorandom Pattern Generators, by Paul H. Bardell, Journal of Electronic Testing: Theory and Applications, 1, 73-87 (1990), including circuits described as `variable-length linear feedback shift registers`. However the circuits disclosed provide only a small number of specific sequences, and although the degree of the characteristic polynomial can be changed, this is restricted to changes which do not involve rearranging the feedback connections.
In implementing a PRPG which can generate patterns having variable width and variable characteristic polynomial, it is necessary to be able to determine the characteristic polynomial which will result in a desired pattern. Known methods of accomplishing this have not been applicable generally to all possible patterns, and/or have incurred a heavy cost in terms of computation required to derive the polynomial.